package com.mango.leet.code.easy;

/**
 * 169. 多数元素
 */
/**
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：[3,2,3]
 * 输出：3
 * 示例 2：
 *
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 *  
 *
 * 进阶：
 *
 * 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/majority-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.*;

/**
 * @Author: mango
 * @Date: 2022/4/1 10:12 下午
 */
public class LC169_MajorityElement {
    public static void main(String[] args) {
        //int[] nums = {2,2,1,1,1,2,2};
        //int[] nums = {3,2,3};
        int[] nums = {3,3,4};
        System.out.println(new Solution().majorityElement(nums));
    }
    static class Solution {
        // hashmap 计数 时间O(n)
        public int majorityElement(int[] nums) {
            TreeMap<Integer,Integer> countMap = new TreeMap<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
            for(int i=0;i<nums.length;i++){
                int num = nums[i];
                countMap.put(num,countMap.getOrDefault(num,0)+1);
            }
            int result = Integer.MIN_VALUE;
            int max = Integer.MIN_VALUE;
            for(Integer key : countMap.keySet()){
                if(max < countMap.get(key)){
                    max = countMap.get(key);
                    result = key;
                }
            }
            return result;
        }
        // 排序 + 取中间数
        public int majorityElement2(int[] nums) {
            Arrays.sort(nums);
            return nums[nums.length/2];
        }
        // 随机选取
        public int majorityElement3(int[] nums) {
            int len = nums.length, half = len >> 1;
            while (true) {
                // 选择随机下标
                int index = (int) (Math.random() * len);
                int num = nums[index];
                int count = 0;
                for (int i = 0; i < len; i++) {
                    count += nums[i] == num ? 1 : 0;
                }
                // 如果找到大于一半长度的数就返回
                if (count > half) {
                    return num;
                }
            }
        }

    }
}
